package Leetcode;

import java.util.Arrays;

/**
 * https://blog.csdn.net/Strom72/article/details/80719276
 * 把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
 * 这道题使用动态规划是比较易于理解的一种解法。思路如下：
 *
 * 丑数只包含因子2、3、5，那么反过来想，1、2、3、5这几个数组合相乘起来就能得到一个丑数，更进一步，一个丑数乘以2、3、5后可以得到另一个丑数，因此，我们可以通过已经存在的丑数推算出下一个丑数，由于要保证从小到大的序列，我们只需要每次都取最小值即可。
 * 还有一个关键的地方，就是要知道2、3、5使用的次数，以保证不会出现重复的现象。
 */
public class 丑数 {
    public int GetUglyNumber_Solution(int index) {
        if (index == 0) return 0;
        int[] factor = {2, 3, 5};
        int[] ugly = new int[index];//这里其实还可以对空间进行优化
        ugly[0] = 1;
        int t2 = 0, t3 = 0, t5 = 0;//记录他们使用过的次数
        for (int i = 1; i < index; i++) {
            ugly[i] = Math.min(ugly[t2] * factor[0], Math.min(ugly[t3] * factor[1], ugly[t5] * factor[2]));
            if (ugly[i] == ugly[t2] * factor[0]) t2++;
            if (ugly[i] == ugly[t3] * factor[1]) t3++;
            if (ugly[i] == ugly[t5] * factor[2]) t5++;
        }
        return ugly[index - 1];
    }

    //判断是否 2、3、5的丑数
    public boolean isUgly(int num) {
        if(num < 1) return false;
        while ( num % 5 == 0){
            num = num / 5;
        }
        while ( num % 3 == 0){
            num = num / 3;
        }
        while ( num % 2 == 0){
            num >>= 1;
        }
        return num ==1;
    }


    //判断是否素数
    /**
     * 换句话说，i 不需要遍历到 n，而只需要到 sqrt(n) 即可。为什么呢，我们举个例子，假设 n = 12。
     * 12 = 2 × 6
     * 12 = 3 × 4
     * 12 = sqrt(12) × sqrt(12)
     * 12 = 4 × 3
     * 12 = 6 × 2
     * 可以看到，后两个乘积就是前面两个反过来，反转临界点就在 sqrt(n)。
     */
    public boolean isPrime(int N) {
        if (N < 2) return false;
        int R = (int) Math.sqrt(N);
        for (int d = 2; d <= R; ++d)
            if (N % d == 0) return false;
        return true;
    }

    /**
     * 统计小于n有多少素数，。。。。弄个数组，把所有数都改为true，然后，挨个遍历，根号N一下的，挨个排除
     */
    int countPrimes(int n) {
        boolean[] isPrim = new boolean[n];
        Arrays.fill(isPrim, true);
        for (int i = 2; i * i < n; i++)
            if (isPrim[i])
                for (int j = i * i; j < n; j += i)
                    isPrim[j] = false;

        int count = 0;
        for (int i = 2; i < n; i++)
            if (isPrim[i]) count++;

        return count;
    }


    //判断是否回文数字，很简单，就直接把数反着求出来，再直接对比看是否一样   还有一种办法，直接转成字符串，两个指针判断也可以
    public int reverse(int N) {
        int ans = 0;
        while (N > 0) {
            ans = 10 * ans + (N % 10);
            N /= 10;
        }
        return ans;
    }

}
